package lib.random;

import lib.gen.Sequence;


/**
 * Creates random trees, which is a graph consisting of N nodes and N-1 edges.
 * @author dolphinigle
 *
 */
public class RandomTree {
  
  /**
   * Random generator
   */
  private ExtendedRandom ex_;
  
  /**
   * Random!
   * @param ex random number generator
   */
  public RandomTree(ExtendedRandom ex) {
    ex_ = ex;
  }
  
  /**
   * Creates a random directed tree.
   * @param nodes number of nodes in the tree.
   * Returns an int[] containing parent information, or -1 if it's root.
   */
  public int[] RandomDirectedTree(int nodes) {
    assert nodes >= 1;
    int[] pres = RandomDirectedTreePreserveOrder(nodes);
    int[] perm = Sequence.range(nodes);
    ex_.nextShuffle(perm);
    int[] ret = new int[nodes];
    for (int i = 0; i < nodes; ++i) {
      if (pres[i] == -1) {
        ret[perm[i]] = -1;
      } else {
        ret[perm[i]] = perm[pres[i]];
      }
    }
    return ret;
  }
  
  /**
   * Creates a random directed tree such that node 0 is root and nodes points
   * only to lower numbered nodes.
   * @param nodes number of nodes
   * @return an int[] containing parent information, or -1 for node 0.
   */
  public int[] RandomDirectedTreePreserveOrder(int nodes) {
    assert nodes >= 1;
    int[] parent = new int[nodes];
    parent[0] = -1;
    for (int i = 1; i < nodes; ++i) {
      parent[i] = ex_.nextInt(i);
    }
    return parent;
  }
}
